package org.datacoder.geocoding.datastructures.rectangles

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.Jurisdiction

class SegmentTree {

    public SegmentTreeNode root
    public int type

    public SegmentTree(Collection<Jurisdiction> jurisdictions, int type){
        this.type = type
        SortedSet<Double> endPointSet = new TreeSet<Double>()
        Set<GeoInterval> geoIntervals = new HashSet<GeoInterval>()
        for(juris in jurisdictions){
            GeoInterval gi = juris.toGeoInterval(type)
            geoIntervals.add(gi)
            endPointSet.add(gi.retrieveMinDoubleValue())
            endPointSet.add(gi.retrieveMaxDoubleValue())
        }
        double[] endPoints = new double[endPointSet.size()]
        Iterator iter = endPointSet.iterator()
        for(int i = 0; i < endPoints.length; i++){
            endPoints[i] = iter.next()
        }
        if(endPoints.length == 0){
            root = null
        }else{
            root = createNode(endPoints, 0, endPoints.length)
        }
        for(gi in geoIntervals){
            addGeoInterval(root, gi)
        }
    }

    public SegmentTreeNode createNode(double[] endPoints, int startIndex, int endIndex){
        SegmentTreeNode stNode = new SegmentTreeNode()
        stNode.leftValue = endPoints[startIndex]
        stNode.rightValue = endPoints[endIndex - 1]
        int middle = (startIndex + endIndex)/2
        if(startIndex < endIndex - 2){
            stNode.left = createNode(endPoints, startIndex, middle + 1)
            stNode.right = createNode(endPoints, middle, endIndex)
        }
        return stNode
    }

    public void addGeoInterval(SegmentTreeNode stNode, GeoInterval gi){
        if(gi.containsInterval(stNode.leftValue, stNode.rightValue)){
            stNode.addJurisdiction(gi.juris)
        }else{
            if((stNode.left != null) && gi.intersectsInterval(stNode.left.leftValue, stNode.left.rightValue)){
                addGeoInterval(stNode.left, gi)
            }
            if((stNode.right != null) && gi.intersectsInterval(stNode.right.leftValue, stNode.right.rightValue)){
                addGeoInterval(stNode.right, gi)
            }
        }
    }

    public Set<Jurisdiction> findIntervalsContainingPoint(double point){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        if(!root.containsPoint(point)){
            return jurisdictions
        }
        Queue<SegmentTreeNode> stNodeQueue = new LinkedList<SegmentTreeNode>()
        stNodeQueue.offer(root)
        while(stNodeQueue.peek() != null){
            SegmentTreeNode currentNode = stNodeQueue.poll()
            jurisdictions.addAll(currentNode.jurisdictions)
            if((currentNode.left != null) && (currentNode.left.containsPoint(point))){
                stNodeQueue.offer(currentNode.left)
            }
            if((currentNode.right != null) && (currentNode.right.containsPoint(point))){
                stNodeQueue.offer(currentNode.right)
            }
        }
        return jurisdictions
    }
}

